package week_six;

//状态 f[i]
//状态转移 f[i] = max{ f[j] + 1} (j<i, nums[j]<nums[i])
//边界 f[i]=1 (0<=i<n)
public class LongestIncreasingSubsequence_300 {
    public int lengthOfLIS(int[] nums) {
        int length = nums.length;
        int[] f = new int[length];
        int max = 1;
        for(int i=0;i<length;i++){
            f[i]=1;
            for(int j=0;j<i;j++){
                if(nums[j]<nums[i]){
                    f[i]=Math.max(f[i], f[j]+1);
                    // System.out.println("i max: "+i+", f[j]: "+f[j]);

                }
            }
            max = Math.max(max, f[i]);
        }
        return max;
    }
}
